Palindrome partitioning III

Time: O(KxN^2); Space: O(N^2); hard

You are given a string s containing lowercase letters and an integer k. You need to : * First, change some characters of s to other lowercase English letters. * Then divide s into k non-empty disjoint substrings such that each substring is palindrome.

Return the minimal number of characters that you need to change to divide the string.

Example 1:

Input: s = “abc”, k = 2

Output: 1

Explanation: You can split the string into “ab” and “c”, and change 1 character in “ab” to make it palindrome.

Example 2:

Input: s = “aabbc”, k = 3

Output: 0

Explanation: You can split the string into “aa”, “bb” and “c”, all of them are palindrome.

Example 3:

Input: s = “leetcode”, k = 8

Output: 0

Constraints:

  • 1 <= k <= len(s) <= 100.

  • s only contains lowercase English letters.

Hints:

  1. For each substring calculate the minimum number of steps to make it palindrome and store it in a table.

  2. Create a dp(pos, cnt) which means the minimum number of characters changed for the suffix of s starting on pos splitting the suffix on cnt chunks.

1. Dynamic programming [O(K*N^2), O(N^2)]

[4]:

class Solution1(object):
    """
    Time: O(K*N^2)
    Space: O(N^2)
    """
    def palindromePartition(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        # dp1[i][j]: minimum number of changes to make s[i, j] palindrome
        dp1 = [[0]*len(s) for _ in range(len(s))]

        for l in range(1, len(s)+1):
            for i in range(len(s)-l+1):
                j = i+l-1
                if i == j-1:
                    dp1[i][j] = 0 if s[i] == s[j] else 1
                elif i != j:
                    dp1[i][j] = dp1[i+1][j-1] if s[i] == s[j] else dp1[i+1][j-1]+1

        # dp2[d][i]: minimum number of changes to divide s[0, i] into d palindromes
        dp2 = [[float("inf")]*len(s) for _ in range(2)]
        dp2[1] = dp1[0][:]

        for d in range(2, k+1):
            dp2[d%2] = [float("inf")]*len(s)
            for i in range(d-1, len(s)):
                for j in range(d-2, i):
                    dp2[d%2][i] = min(dp2[d%2][i], dp2[(d-1)%2][j]+dp1[j+1][i])

        return dp2[k%2][len(s)-1]

[5]:

sol = Solution1()

s = "abc"
k = 2
assert sol.palindromePartition(s, k) == 1

s = "aabbc"
k = 3
assert sol.palindromePartition(s, k) == 0

s = "leetcode"
k = 8
assert sol.palindromePartition(s, k) == 0